package main

type Node struct{
	Val int
	Left *Node
	Right *Node
	Next *Node
}
/*
	给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。
	填充它的每个next指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将next指针设置为null
	初始状态下，所有next指针都被设置为null
*/
//通过层序遍历方法实现
//func connect(root *Node) *Node{
//	if root==nil{
//		return root
//	}
//	//因为是完美二叉树，所以每一行的最后一个应该=2的n次方-1
//	count := 0
//	//根节点的next为nil
//	nodeList := []*Node{}
//	//根节点入队
//	nodeList = append(nodeList,root)
//	for{
//		if len(nodeList)==0{
//			break
//		}
//		//取出队列头部节点并弹出
//		pNode := nodeList[0]
//		nodeList = nodeList[1:]
//		//将左右节点入队
//		if pNode.Left !=nil && pNode.Right != nil{
//			nodeList = append(nodeList,pNode.Left)
//			nodeList = append(nodeList,pNode.Right)
//		}
//		count++
//		//判断一个数是否是2的方幂，可以使用n>0&&((n&(n-1))==0)
//		if (count+1)&count != 0{
//			//一层的最后一个节点next为Nil
//			//否则
//			pNode.Next = nodeList[0]
//		}
//	}
//	return root
//}

//通过已建立的树的next进行操作
func connect(root *Node) *Node{
	//1.同一父节点，左孩子指向右孩子
	//循环第N层时，构造第N+1层节点
	curNode := root
	for {
		//当前节点没有孩子节点，则遍历到最后一层
		if curNode.Left == nil{
			break
		}
		leftNode := curNode
		for {
			//1.不同父节点，当前节点的右孩子，指向next节点的左孩子
			curNode.Left.Next = curNode.Right
			if curNode.Next == nil {
				break
			}
			curNode.Right.Next= curNode.Next.Left
			curNode = curNode.Next
		}
		curNode = leftNode.Left
	}
	return root
}

